package edu.siu.math.egut.util;

import java.io.Serializable;
import java.util.Arrays;

/**
 * A data structure for storing the Cayley table for addition of roots.
 * 
 * Conceptually, this is a two-dimensional array indexed by (two copies of)
 * the set of roots.  The entry corresponding to the pair (a,b) (where a
 * and b are roots) will be a+b if this is a root and null if it is not.
 * 
 * Initializing and using a table saves time over doing the arithmetic 
 * operation (and checking the root status) each time. 
 * @author Joe Pleso
 * @author Joseph Hundley
 * 
 */
public class VectorCayleyTable implements Serializable {

    /**
     * 
     */
    private static final long serialVersionUID = 126L;
    /**
     * Underlying data of the table.  Although we think of the table as a 
     * two dimensional array of int[] 's (perhaps an int[][][]) we
     * shall actually store it as an int[][].  This int[][] should 
     * be thought of as a list of roots. It will contain 
     * only the entries lying strictly above the diagonal, with other entries
     * being deduced by symmetry if they are below the diagonal, or 
     * from the well-known fact that a reduced root system never 
     * contains 2*alpha for alpha a root. 
     */
    private final int[][] matrix;
    /**
     * the number of rows/columns in the Cayley table
     */
    public final int length;

    /**
     * the set of int[]'s used to initialize the Cayley table.
     */
     private final int[][] roots;

    /**
     * Create a new Cayley table for vectors over addition.
     * @param  r  an int[][] representing a finite nonempty list of vectors  (tuples of integers) 
      */
    public VectorCayleyTable(int[][] r) {
	
	// initialize roots from data given
        roots = r;
        
        // initialize length.
        length = roots.length;
        
        // introduce a local variable with a name that is shorter than "length."
        int n = length;
        
        // initialize matrix. 
        matrix = new int[((n * (n - 1)) / 2)][roots[0].length];
        // clearly, n*(n-1)/2 is the number of entries strictly above the diagonal in an n x n array.
        // roots[0].length is also the length of every other root, and hence the correct dimension 
        // for each row in our int[].
        // NOTE:  this will throw an ArrayIndexOutOfBoundsException if one tries to initialize a Cayley table
        // for the empty set of roots.   
        
        //local variable for scratch work
        int[] temp = new int[roots[0].length];
        
        // for each entry above the diagonal,
        for (int i = 0; i < roots.length - 1; i++) {
    	for (int j = i + 1; j < roots.length; j++) {
    	    // set temp equal to the sum of the two roots in question.
    	    for (int k = 0; k < temp.length; k++)
    		temp[k] = (roots[i][k] + roots[j][k]);
    	    
    	    // see whether the sum is a root and if so which one.
    	    int k = findIndex(temp);
    	    int[] image;
    	    if (k < 0)
    		image = null;
    	    else
    		image = roots[k];
    	    set(i, j, image);
    	}
        }

    }

    /**
     * Adds two vectors, using a Cayley table.  Result will be the sum 
     * of the two vectors, if it was a member of the list used to 
     * initialize the table, and null if not.
     * 
     * @param iRoot the first vector
     * @param jRoot the second vector
     * @return the sum or null if the sum is not on the list provided
     * 
     */
    public int[] add(int[] iRoot, int[] jRoot) {
	int i = findIndex(iRoot);
	int j = findIndex(jRoot);
	if (i > -1 && j > -1) {
	    if (j < i)
		return (add(jRoot, iRoot));
	    if (i == j)
		return null;
	    i++;
	    j++;
	    int n = length;
	    return matrix[((((2 * n) - i) * (i - 1)) / 2) - i + j - 1];
	}
	throw new RuntimeException();
    }

    /**
     * Return the list of roots that was used to initialize this table.
     * 
     * @return the list of roots
     */
     public int[][] getRoots() {
        return roots;
    }
/*This method sets the "(i,j) entry" of our "table" equal to a given (possibly null) int[].
 * The only wrinkle is that since we store only he 
 * entries above the diagonal, one has to do a bit of arithmetic to figure out which
 * entry of the actual one dimensional array corresponds to the (i,j)-entry of the 
 * conceptual two-dimensional array.
 * 
 */
    private void set(int i, int j, int[] x) {
	if (j < i)
	    set(j, i, x);
	else {
	    // add one to each for convenience.  (this converts from 0 to n-1 numbering to 
	    // 1 to n numbering.)
	    i++;
	    j++;
	    int n = length;
	    matrix[((((2 * n) - i) * (i - 1)) / 2) - i + j - 1] = x;
	}
    }

    /**
     * Subtracts two vectors from the list of vectors that was used to
     * construct this table.
     * 
     * @param a  the first vector
     * @param b  the second vector
     * @return returns the vector a-b if it was in the original list (and
     *         null if not).
     */
    public int[] subtract(int[] a, int[] b) {
        int bIndex = findIndex(b);
        for (int i = 0; i < bIndex; i++)
    	if (Arrays.equals(add(roots[i], b), a))
    	    return roots[i];
        for (int i = bIndex + 1; i < roots.length; i++)
    	if (Arrays.equals(add(b, roots[i]), a))
    	    return roots[i];
        return null;
    }
    

/**
 * Finds the index of root in the int[][] roots
 * 
 * @param roots
 *            a int[][] to search in
 * @param root
 *            a int[] to find in roots
 * @return the index such that roots[index]==root is true, or -1 if a match
 *         was not found
 */
private int findIndex(int[][] roots, int[] root) {
	for (int i = 0; i < roots.length; i++)
	    if (Arrays.equals(root, roots[i]))
		return i;
	return -1;
}

/**
 * Finds the index of an int[] in the int[][] used to initialize the Cayley table
 * @param root an int[]
 * @return the index such that roots[index]==root is true, or -1 if a match
 *         was not found
 */
public int findIndex(final int[] root) {
	return findIndex(roots, root);
}
}
